package com.wtgroup.demo.leetcode.q005_最长回文子串;

/**
 * @author nisus
 * @version 0.1
 * @since 2023/5/17 11:06
 */
public class D_暴力 {
    /*
     每个位置开始, 递增观察对应长度的子串是否是回文子串
     */

    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }

        int ansSt = 0;
        int ansLen = 1; // 至少有一个

        char[] chars = s.toCharArray();
        int N = chars.length;

        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                // 减枝
                int ansLen1 = j - i + 1;
                if (ansLen1 <= ansLen) {
                    // 已经有更长的, 没必要判断更短的
                    continue;
                }

                // i ~ j 是否是回文子串
                if (isValidPalindrome(chars, i, j)) {
                    ansSt = i;
                    ansLen = ansLen1;
                }
            }
        }

        return s.substring(ansSt, ansSt + ansLen);
    }

    private boolean isValidPalindrome(char[] chars, int left, int right) {
        while (left <=right && chars[left] == chars[right]) {
            left++;
            right--;
        }
        return left > right;
    }

}
